home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _partition.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.4 KB  |  77 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _partition.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //------------------------------------------------------------------------------
  18. //
  19. // partitions
  20. //
  21. // implementation: union find with weighted union rule and path compression
  22. //
  23. // S. N.  (1989)
  24. //------------------------------------------------------------------------------
  25.  
  26. #include <LEDA/partition.h>
  27.  
  28.  
  29. void partition::clear()
  30. { // free all used items
  31.   partition_item p = used_items; 
  32.   while (used_items)
  33.   { p = used_items;
  34.     used_items = used_items->next;
  35.     clear_inf(p->info);
  36.     delete p;
  37.    }
  38.  }
  39.   
  40.  
  41.  
  42. partition_item partition::find(partition_item y) 
  43. { // find with path compression
  44.  
  45.   register partition_item x = y->father;
  46.  
  47.   if (x==0) return y;
  48.  
  49.   register partition_item root = y;
  50.  
  51.   while (root->father) root = root->father;
  52.  
  53.   while (x!=root)
  54.   { y->father = root;
  55.     y = x;
  56.     x = y->father;
  57.    }
  58.   return root;
  59.  }
  60.  
  61. void partition::union_blocks(partition_item a, partition_item b)
  62. { // weighted union
  63.  
  64.   a = find(a);
  65.   b = find(b);
  66.  
  67.   if (a==b) return;
  68.  
  69.   if (a->size > b->size)
  70.        { b->father = a;
  71.          a->size += b->size; }
  72.   else { a->father = b;
  73.          b->size += a->size; }
  74.  
  75.  }
  76.  
  77.